package leetcode.code1203;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

//执行用时：58 ms, 在所有 Java 提交中击败了6.98%的用户
//
//内存消耗：65.5 MB, 在所有 Java 提交中击败了5.81%的用户
//
//通过测试用例：17 / 17
public class Solution implements IDebug {

	public int[] sortItems(int n, int m, int[] group, List<List<Integer>> beforeItems) {
		Map<Integer, Group> groups = new HashMap<>();
		Item[] items = new Item[n];
		for (int i = 0; i < n; i++) {
			items[i] = new Item(i);
		}
		int undefineId = -2;
		for (int i = 0; i < n; i++) {
			int groupId = group[i];
			if (groupId == -1) {
				groupId = undefineId--;
			}
			Group curGroup = groups.getOrDefault(groupId, new Group(groupId));
			items[i].groupId = groupId;
			curGroup.addItem(items[i]);
			groups.put(groupId, curGroup);
		}
		for (int i = 0; i < n; i++) {
			List<Integer> beforeItem = beforeItems.get(i);
			Item curItem = items[i];
			curItem.in = beforeItem.size();
			Group curGroup = groups.get(curItem.groupId);
			for (int j = 0; j < beforeItem.size(); j++) {
				int bi = beforeItem.get(j);
				Item item = items[bi];
				item.edges.add(curItem);
				Group beGroup = groups.get(item.groupId);
				beGroup.addEdges(curGroup);
				curGroup.addInGroup(beGroup);
			}
		}
		Queue<Group> groupQueue = new LinkedList<>();
		Set<Integer> done = new HashSet<>();
		for (Map.Entry<Integer, Group> entry : groups.entrySet()) {
			if (entry.getValue().in == 0) {
				groupQueue.add(entry.getValue());
				done.add(entry.getValue().groupId);
			}
		}
		Queue<Group> ansQueue = new LinkedList<>();
		while (!groupQueue.isEmpty()) {
			Group curGroup = groupQueue.poll();
			ansQueue.add(curGroup);
			for (Group next : curGroup.edges) {
				next.in--;
				if (next.in == 0 && !done.contains(next.groupId)) {
					groupQueue.add(next);
				}
			}
		}
		if (ansQueue.size() != groups.size()) {
			return new int[] {};
		}
		int[] ans = new int[n];
		int p = 0;
		boolean[] seen = new boolean[n];
		while (!ansQueue.isEmpty()) {
			Group curGroup = ansQueue.poll();
			List<Item> curItems = curGroup.items;
			Queue<Item> q = new LinkedList<>();
			for (Item item : curItems) {
				if (item.in == 0) {
					seen[item.itemId] = true;
					q.add(item);
				}
			}
			int did = 0;
			while (!q.isEmpty()) {
				Item curItem = q.poll();
				ans[p++] = curItem.itemId;
				did++;
				for (Item next : curItem.edges) {
					next.in--;
					if (next.in == 0 && !seen[next.itemId] && next.groupId == curGroup.groupId) {
						seen[next.itemId] = true;
						q.add(next);
					}
				}
			}
			if (did != curItems.size()) {
				return new int[] {};
			}
		}
		return ans;
	}

	class Group {

		List<Item> items;
		int groupId;
		Set<Group> inEdge;
		Set<Group> edges;
		int in;

		public void addItem(Item item) {
			this.items.add(item);
		}

		public void addInGroup(Group group) {
			if (group.groupId != this.groupId) {
				this.inEdge.add(group);
				in = inEdge.size();
			}
		}

		public void addEdges(Group group) {
			if (group.groupId != this.groupId) {
				this.edges.add(group);
			}
		}

		public Group(int groupId) {
			this.items = new ArrayList<>();
			this.groupId = groupId;
			this.inEdge = new HashSet<>();
			edges = new HashSet<>();
		}
	}

	class Item {
		int itemId;
		int in;
		List<Item> edges;
		int groupId;

		public Item(int itemId) {
			this.itemId = itemId;
			this.in = 0;
			edges = new ArrayList<>();
		}
	}

	@Override
	public void debug1() {
		int[] e = HelpDebug.str2array3("[6,3,4,1,5,2,0,7]");
		List<List<Integer>> beforeItems = new ArrayList<>();
//		"[[],[6],[5],[6],[3,6],[],[],[]]"
		beforeItems.add(Arrays.asList());
		beforeItems.add(Arrays.asList(6));
		beforeItems.add(Arrays.asList(5));
		beforeItems.add(Arrays.asList(6));
		beforeItems.add(Arrays.asList(3, 6));
		beforeItems.add(Arrays.asList());
		beforeItems.add(Arrays.asList());
		beforeItems.add(Arrays.asList());
		HelpDebug.compare(e, this.sortItems(8, 2, HelpDebug.str2array3("[-1,-1,1,0,0,1,0,-1]"), beforeItems));
	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
